1993. Weighing
n balls are given. n – 1 of them have the same weight, and
one is heavier. Find the minimum number of weighings required to determine
which ball is heavier using a two pan balance. Weighing operation is described
as follows: the same amount of balls is placed on each of the two pans. If one pan
outweigh the other, the heavy ball lies on the first one. If the pans in balance,
the heavy ball is out of pans. After each weighing the decision is made which
balls will participate in the next weighting.
Input. One integer n (2 ≤ n ≤ 109).
Output. The minimum number of
weighings to find the heavy ball.
|
Sample
input 1 |
Sample
output 1 |
|
2 |
1 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
4 |
2 |
SOLUTION
mathematics
Algorithm analysis
Put all the balls into
three equal (by amount) piles. If n is not divisible by 3, the piles
will differ from each other by no more than one ball. Put equal piles on each of
two pans. In one weighing we will determine in which of three piles the heavier
ball is located. So in one weighting we can move from the task with n balls in the worst case to a problem
with 
balls. Therefore to
ensure detection of heavier ball its enough 
weighings.
Example
One weighing is sufficient
for three balls. If the scales are in balance, then the heavier ball is not on
the scales.
In the case of 9 balls, we
decompose them into 3 piles of 3 balls. Putting one pile to each side of
weights, we will determine the pile where the heavy ball is.
If there are 8 balls, then
we will decompose them into three piles as follows: 3, 3, 2. In this case, we
place the piles 3 and 3 on the scales.
Algorithm realization
Given
input number n, compute and print the value 
.
scanf("%d",&n);
res = ceil(log(1.0*n) /
log(3.0));
printf("%.0lf\n",res);
Algorithm realization – loop
#include <stdio.h>
#include <math.h>
int n, p, res;
int main(void)
{
scanf("%d",&n);
res = 0; p = 1;
while(p <
n)
{
p = p * 3;
res++;
}
printf("%d\n",res);
return 0;
}
Java realization
import java.util.*;
public class Main
{
public static void main(String []args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
double res = Math.ceil(Math.log(n) / Math.log(3));
System.out.printf("%.0f\n",res);
con.close();
}
}
Python realization
import math
n = int(input())
print (int(math.ceil(math.log(n) / math.log(3))))